package ljl.alg.jianzhioffer.round2;

/**
 * 这是两道题，一个要求余，考虑大数问题；一个不用
 * 我放到一起吧，代码只是多了求余的步骤
 * <p>
 * 这个题第一个关键是要求出来，n 优先取 3，其次取 2
 * <p>
 * 假设每段 x，已知 xa = n，每段大小一样时乘积最大
 * 乘积值为 x^(n/x) = (x^(1/x))^n
 * <p>
 * 令 y = x ^ (1/x)
 * 解法是，先求对数再求导，不然求不出来
 * lny = 1/x * lnx
 * 再求导
 * 1/y * y' = 1/x^2 - 1/x^2 * lnx = (1 - lnx) / x^2
 * <p>
 * 简单地令 y' = 0，则 x = e，约等于 2.71828
 * 然后 x 必须是整数，看 2 和 3 谁更大
 * <p>
 * y(2) = 2 ^ (1/2)
 * y(3) = 3 ^ (1/3)
 * <p>
 * 同时取 6 次幂：
 * y(2)^6 = 2^3 = 8
 * y(3)^6 = 3^3 = 9
 * <p>
 * 所以 3 更大点，优先选 3
 * <p>
 * 你知道 3 最大还不行，还得考虑特殊情况，包含
 * n <= 3 返回 n - 1，因为至少切一刀
 * 对 3 整除后的余数 b
 * b = 0
 * b = 1，此时要去掉一个 3，乘上一个 4，因为 2 * 2 > 1 * 3
 * b = 2
 * <p>
 * 下次复习一下吧，这个题不能算掌握
 */
public class _14_1_cut_rope {
    
    /**
     * 这个解法也挺好的，但也得提前知道要选 3 或 2
     */
    public int cuttingRope1(int n) {
        if (n <= 3) return n - 1;
        long res = 1L;
        int p = (int) 1e9 + 7;
        //贪心算法，优先切三，其次切二
        while (n > 4) {
            res = res * 3 % p;
            n -= 3;
        }
        //出来循环只有三种情况，分别是n=2、3、4
        return (int) (res * n % p);
    }
    
    /**
     * 这个解法能通过，但还是不对
     * n 能取到 1000，3^1000 比 long 最大值还大
     */
    public int cuttingRope2(int n) {
        if (n <= 3) return n - 1;
        final int p = (int) 1e9 + 7;
        int count3 = n / 3, r = n % 3;
        if (r == 0) return (int) ((long) Math.pow(3, count3) % p);
        if (r == 1) return (int) ((long) Math.pow(3, count3 - 1) * 4 % p);
        return (int) ((long) Math.pow(3, count3) * 2 % p);
    }
    
    /**
     * 不要用 math.pow
     * 用快速幂乘法，同时不停的取余就行了
     */
    public int cuttingRope3(int n) {
        if (n <= 3) return n - 1;
        final int p = 1000000007;
        int b = n % 3;
        
        long res = 1, x = 3;
        // 本来循环 n 次，这次去掉特殊情况只循环 n-1 次，因为余数为 2 时得 -1
        int e = n / 3 - 1;
        while (e > 0) {
            if ((e & 1) == 1)
                res = res * x % p;
            x = x * x % p;
            e >>= 1;
        }
        
        if (b == 0) return (int) (res * 3 % p);
        if (b == 1) return (int) (res * 4 % p);
        return (int) (res * 6 % p);
    }
    
}
